/*
 * @lc app=leetcode.cn id=124 lang=golang
 *
 * [124] 二叉树中的最大路径和
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func maxPathSum(root *TreeNode) int {
	pathSum := 0
	var oneside func(root *TreeNode) int
	oneside = func(root *TreeNode) int {
		if root == nil {
			return 0
		}

		left := oneside(root.Left)
		right := oneside(root.Right)
		curMaxSide := max(max(left+root.Val, right+root.Val), root.Val)
		pathSum = max(pathSum, max(curMaxSide, left+right+root.Val))
		return curMaxSide
	}
	oneside(root)
	return pathSum

}

func max(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

// @lc code=end

